Guided Practice 4.5 Halting Measures

Consider the following function, defined on ListOfNumbers:

;; odd-elements : ListOfNumbers -> ListOfNumbers
(define (odd-elements lst)
  (cond
    [(empty? lst) empty]
    [(empty? (rest lst)) (first lst)]
    [else (cons (first lst)
                (odd-elements (rest (rest lst))))]))

Which of the following are valid halting measures for odd-elements ?

a) when lst is empty
b) when lst has one or fewer elements
c) the length of lst
d) the number of elements of lst
e) the largest element of lst

Next, consider the data type

An AltList is one of
-- empty
-- (list Number AltList)

and the function

alt-odd-elements : AltList -> AltList
(define (alt-odd-elements x)
  (cond
    [(empty? x) empty]
    [(empty? (second x)) (list (first x) empty)]
    [else (list (first x)
                (alt-odd-elements (second (second x))))]))

Which of the following are valid halting measures for odd-elements ?

a) when x is empty
b) when x has one or fewer elements
c) the length of x
d) the number of elements of x
e) the largest element of x

[SOLUTION]